【题解】 [SDOI2008]Cave洞穴勘测 LCT bzoj2049/洛谷P2147 | Qiuly's blog!

【题解】 [SDOI2008]Cave洞穴勘测 LCT bzoj2049/洛谷P2147

Posted on | Edited on | In | Comments:

Link-Cut-Tree的模板题啊……(听说还可以用其他的方法做，不管了，直接上LCT)

没有要求维护点权，只需要维护点的连通性即可。

就是朴素的LCT，居然还不要pushup。

感觉有些不适应啊…….不得不说LCT是个神器。

简单分析一下。

  • 对于每种命令:
    • 如果是Connect x y (链接 x y):直接 link(x,y)即可。
    • 如果是Destroy x y (切断 x y):直接 cut(x,y)即可。
    • 如果是Query x y (询问 x y 的连通性):判断findroot(x)和findroot(y)是否一致，一致输出Yes，否则输出No。

然后就A了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A")
#define C printf(" ") 
using namespace std;
const int N=2e5+2;
template <typename Tp> inline void IN(Tp &x){
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int n,m,f[N],r[N],hep[N],ch[N][2];
inline int chk(int x){return ch[f[x]][1]==x;}
inline int get(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void filp(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;} 
inline void pushdown(int x){
	if(!r[x])return;r[x]=0;
	if(ch[x][0])filp(ch[x][0]);
	if(ch[x][1])filp(ch[x][1]);
}
inline void rotate(int x){
	int y=f[x],z=f[y],k=chk(x),&v=ch[x][!k];
	if(get(y))ch[z][chk(y)]=x;v=y,ch[y][k]=v;
	if(v)f[v]=y;f[y]=x,f[x]=z;return;
}
inline void Splay(int x){
	int y=x,top=0;hep[++top]=y;
	while(get(y))hep[++top]=y=f[y];
	while(top)pushdown(hep[top--]);
	while(get(x)){
		y=f[x],top=f[y];
		if(get(y))rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
		rotate(x);
	}return;
} 
inline void Access(int x){
    for(register int y=0;x;x=f[y=x])
       Splay(x),ch[x][1]=y;
}
inline void makeroot(int x){
    Access(x);Splay(x);filp(x);
}
inline int findroot(int x){
    Access(x);Splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    return x;
}
inline void split(int x,int y){
    makeroot(x);Access(y);Splay(y);
} 
inline void link(int x,int y){
    makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
        f[x]=ch[y][0]=0;
    }return;
}char op[10];
int main(){
    scanf("%d%d",&n,&m);
    for(register int x,y,i=1;i<=m;++i){
    	scanf("%s%d%d",op,&x,&y);
        if(op[0]=='C')link(x,y);
		else if(op[0]=='D')cut(x,y);
		else if(op[0]=='Q'){
			if(findroot(x)==findroot(y))printf("Yes\n");
			else printf("No\n");
		}	
	}return 0;
}

本文标题:【题解】 [SDOI2008]Cave洞穴勘测 LCT bzoj2049/洛谷P2147

文章作者:Qiuly

发布时间:2019年02月13日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP2147/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。